package exercise;

import java.util.ArrayList;
import java.util.List;


class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

/**
 * 删除链表中重复的结点
 * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
 * 例如，链表 1->2->3->3->4->4->5  处理后为 1->2->5
 */
public class Solution {
    public ListNode deleteDuplication(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode curprev=head;
        ListNode cur=head.next;
        int[] array=new int[1000];

        while (cur!=null){
            if(curprev.val==cur.val){
                array[cur.val]++;
            }
            curprev=cur;
            cur=cur.next;
        }
        // System.out.println(array[5]);
        ListNode prev=null;
        cur=head;
        ListNode curNext=cur.next;
        while (cur!=null){
            curNext=cur.next;
            if(array[cur.val]==0){
                if(cur==head){
                    head=cur;//cur为头结点时
                }else if(prev==null&&cur!=head){
                    head=cur;//cur为头结点时
                }else {
                    cur.next=null;//防止最后一个结点的next不为空
                    prev.next=cur;
                }
                prev=cur;
                cur=curNext;
            }else {
                cur=curNext;
            }

        }
        if(prev==null&&cur==null){
            return null;
        }
        return head;
    }

    /**
     * 二维网络迁移
     * 给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。
     * 每次「迁移」操作将会引发下述活动：
     * 位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
     * 位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
     * 位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。
     * 请你返回 k 次迁移操作后最终得到的 二维网格。
     * 题解，把二维数组整体当作一维数组，每次的移动相当于整体向后移动
     * @param grid
     * @param k
     * @return
     */
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                row.add(0);
            }
            ret.add(row);
        }
        //上面是建立ret
        //没有动原数组，把而是把目标移动结果直接放到ret中了
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
              int index= i * n + j;//二维坐标对应的一维坐标的位置
                int index1 = (index + k) % (m * n);//移动k个位置后的一维坐标位置
                ret.get(index1 / n).set(index1 % n, grid[i][j]);//把index1 / n行的第index1 % n位置放倒推出相应的二维坐标的位置
            }
        }
        return ret;
    }

    /**
     * 比较含退格的字符串
     * @param s
     * @param t
     * @return
     */

    public boolean backspaceCompare(String s, String t) {
        return build(s).equals(build(t));
    }

    public String build(String str) {
        StringBuffer ret = new StringBuffer();
        int length = str.length();
        for (int i = 0; i < length; ++i) {
            char ch = str.charAt(i);
            if (ch != '#') {
                ret.append(ch);
            } else {
                if (ret.length() > 0) {
                    ret.deleteCharAt(ret.length() - 1);
                }
            }
        }
        return ret.toString();
    }






    public static void main(String[] args) {

    }
}
